#ifndef SISTEMA_H
#define SISTEMA_H

#include "ISistema.h"
#include "Tabla.h"
#include "TablaHash.h"
#include "Ciudad.h"
#include "Grafo.h"
#include "GrafoImp.h"
#include "Tramo.h"

class Sistema : public ISistema
{
public:
	Sistema(nat VELOCIDAD_OMNIBUS, nat VELOCIDAD_AVION, nat COSTO_OMNIBUS, nat COSTO_AVION, nat CAPACIDAD_OMNIBUS, nat CAPACIDAD_AVION, nat MAX_CIUDADES);
	virtual ~Sistema();

	// Tipo 1
	TipoRetorno IngresoTramo(Cadena nombreCiudadOrigen, Cadena nombreCiudadDestino, nat distancia, TipoTransporte tipoTransporte);
	Tupla<TipoRetorno, Puntero<Iterador<Tupla<TipoTransporte, Puntero<Iterador<pCiudad>>, nat>>>> Presupuesto(Cadena nombreCiudadOrigen, Cadena nombreCiudadDestino);
	Tupla<TipoRetorno, bool> HayCamino(Cadena nombreCiudadOrigen, Cadena nombreCiudadDestino, TipoTransporte tipoTransporte);
	Tupla<TipoRetorno, Puntero<Iterador<Tupla<Puntero<Iterador<pCiudad>>, nat>>>> CaminoMasCorto(Cadena nombreCiudadOrigen);
	Tupla<TipoRetorno, nat, Puntero<Iterador<Tupla<Cadena, nat>>>> ItemsValiosos(Puntero<Iterador<Tupla<Cadena, nat, nat, nat>>> items, nat pesoMaximo);

	// Tipo 2
	Tupla<TipoRetorno, nat> TendidoMenorCosto();
	Tupla<TipoRetorno, Puntero<Iterador<Tupla<Puntero<Iterador<pCiudad>>, nat>>>> CaminoMasBaratoNoPasaPor(Cadena nombreCiudadOrigen, Puntero<Iterador<Cadena>> excluidas, TipoTransporte tipoTransporte);
	Tupla<TipoRetorno, nat, Puntero<Iterador<pCiudad>>> Itinerario(Puntero<Iterador<Cadena>> ciudades);

	// Opcional
	Tupla<TipoRetorno, Puntero<Iterador<pCiudad>>> CiudadesFijas();

	// Requeridas
	TipoRetorno IngresoCiudad(Cadena nombre, nat costoDiario);
	Tupla<TipoRetorno, Puntero<Iterador<pCiudad>>> ListCiudades();

private:
	Puntero<Tabla<Cadena, Puntero<Ciudad> > > ciudadesHash;
	Puntero < Grafo < Puntero<Ciudad>, Puntero<Tramo> > > grafo;
	
	//nodo Dijkstra 
	struct nodoD{
		bool conocido;
		int distancia;
		int anterior;
	};
	
	Array<nodoD> tablaPrim;
	//Auxiliares

	//Auxiliares HayCamino
	void RealizarClausuraTransitiva(TipoTransporte &tipoTransporte, Matriz<bool> &matrizExisteCamino);
	bool ExisteCamino(Puntero<Ciudad> &origen, Puntero<Ciudad> &destino, Matriz<bool> &matriz);
	//Auxiliares Presupuesto
	void guardarCamino(Array<int> &camino, int &tope, Puntero<Lista<Tupla<TipoTransporte, Puntero<Iterador<pCiudad>>, nat>>> &retorno, int &costo, TipoTransporte &tipoT);
	void buscarCaminos(Puntero<Ciudad> &origen, Puntero<Ciudad> &destino, Puntero<Lista<Tupla<TipoTransporte, Puntero<Iterador<pCiudad>>, nat>>> &retorno, TipoTransporte &tipoT);
	void buscarTodosCaminos(Array<bool> &visit, Array<int> &c, int &tope, int &ini, int &fin, Puntero<Lista<Tupla<TipoTransporte, Puntero<Iterador<pCiudad>>, nat>>> &retorno, TipoTransporte &tipoT, int &costo);
	//Auxiliares Tendido menos costoso
	void inicializarTablaPrim();
	nat prim();
	int minDistDesc();
	bool esConexo();
	void auxPrim(int &indice);
	//Auxiliares CaminoMasCorto
	int BuscoMenorNoConocido(Array<nodoD> arreglo );

	//Auxiliares ItemsValiosos
	Matriz<nat> Mochila(int cantItems, nat pesoMaximo, Array<nat> cantItem, Array<nat> valorItem, Array<nat> pesoItem, Matriz<bool> items);
	void Componer(int cantItems, nat pesoMaximo,Matriz<bool> items, Array<nat> pesoItems, Matriz<nat> matrizItems, Array<nat>& solucion);

	//Auxiliares Itinerario
	void RealizarClausuraTransitivaConPesos(Matriz<nat> &matrizCamino, Matriz<int> &matrizPred);
	void ObtenerCamino(int origen, int destino, Matriz<int> &matrizPred, Matriz<nat> &matrizCamino, Puntero<Lista<Puntero<Ciudad>>>  &aux);
	bool ExistenCiudadesEnCamino(Puntero<Lista<Puntero<Ciudad>>> lista, Puntero<Lista<Puntero<Ciudad>>> listaAux);

	nat V_VELOCIDAD_OMNIBUS; 
	nat V_VELOCIDAD_AVION;
	nat V_COSTO_OMNIBUS; 
	nat V_COSTO_AVION; 
	nat V_CAPACIDAD_OMNIBUS; 
	nat V_CAPACIDAD_AVION; 
	nat V_MAX_CIUDADES;

};

#endif
